﻿//class Solution
//{
//	bool check[16];
//	int ret;
//public:
//	int countArrangement(int n)
//	{
//		dfs(1, n);
//		return ret;
//	}
//	void dfs(int pos, int n)
//	{
//		if (pos == n + 1)
//		{
//			ret++;
//			return;
//		}
//		for (int i = 1; i <= n; i++)
//		{
//			if (!check[i] && (pos % i == 0 || i % pos == 0))
//			{
//				check[i] = true;
//				dfs(pos + 1, n);
//				check[i] = false; 
//			}
//		}
//	}
//};




//class Solution
//{
//	bool checkCol[10], checkDig1[20], checkDig2[20];
//	vector<vector<string>> ret;
//	vector<string> path;
//	int n;
//public:
//	vector<vector<string>> solveNQueens(int _n)
//	{
//		n = _n;
//		path.resize(n);
//		for (int i = 0; i < n; i++)
//			path[i].append(n, '.');
//
//		dfs(0);
//		return ret;
//	}
//	void dfs(int row)
//	{
//		if (row == n)
//		{
//			ret.push_back(path);
//			return;
//		}
//		for (int col = 0; col < n; col++) // 尝试在这⼀⾏放皇后
//		{
//			// 剪枝
//			if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col])
//			{
//				path[row][col] = 'Q';
//				checkCol[col] = checkDig1[row - col + n] = checkDig2[row +
//					col] = true;
//				dfs(row + 1);
//				// 恢复现场
//				path[row][col] = '.';
//				checkCol[col] = checkDig1[row - col + n] = checkDig2[row +
//				col] = false;
//			}
//		}
//	}
//};





//class Solution
//{
//	bool row[9][10];
//	bool col[9][10];
//	bool grid[3][3][10];
//public:
//	bool isValidSudoku(vector<vector<char>>& board)
//	{
//		for (int i = 0; i < 9; i++)
//			for (int j = 0; j < 9; j++)
//			{
//				if (board[i][j] != '.')
//				{
//					int num = board[i][j] - '0';
//					// 是否是有效的
//					if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
//						return false;
//					row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
//				}
//			}
//		return true;
//	}
//};


class Solution
{
	bool row[9][10], col[9][10], grid[3][3][10];
public:
	void solveSudoku(vector<vector<char>>& board)
	{
		// 初始化
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] != '.')
				{
					int num = board[i][j] - '0';
					row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
				}
			}
		}
		dfs(board);
	}
	bool dfs(vector<vector<char>>& board)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] == '.')
				{
					// 填数
					for (int num = 1; num <= 9; num++)
					{
						if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3]
							[num])
						{
							board[i][j] = '0' + num;
							row[i][num] = col[j][num] = grid[i / 3][j / 3]
								[num] = true;
							if (dfs(board) == true) return true; 
							// 恢复现场
							board[i][j] = '.';
							row[i][num] = col[j][num] = grid[i / 3][j / 3]
								[num] = false;
						}
					}
					return false; 
				}
			}
		}
		return true; 
	}
};